状压DP Codeforces 1234F
本文最后更新于:2024年9月13日 早上
题目描述
You are given a string s consisting only of first 20 lowercase Latin letters (‘a’, ‘b’, …, ‘t’).
Recall that the substringof the string s is the string slsl+1…sr. For example, the substrings of “codeforces” are “code”, “force”, “f”, “for”, but not “coder” and “top”.
You can perform the following operation no more than once: choose some substringand reverse it (i.e. the string becomes ).
Your goal is to maximize the length of the maximum substring of s consisting of distinct (i.e. unique) characters.
The string consists of distinct characters if no character in this string appears more than once. For example, strings “abcde”, “arctg” and “minecraft” consist of distinct characters but strings “codeforces”, “abacaba” do not consist of distinct characters.
输入格式 Input Format
- The only line of the input contains one string s consisting of no more than
characters ‘a’, ‘b’, …, ‘t’ (first 20 lowercase Latin letters).
输出格式 Output Format
- Print one integer — the maximum possible length of the maximum substring of s consisting of distinct characters after reversing no more than one its substring.
输入:
abcdeefc
输出:
6
中文题意
你有一个字符串,里面的字符全是0~20(a~t)以内的小写字母,你可以通过旋转一段区间的方式把它变成一个新的字符串,我们这里对旋转的定义是将一段区间的
想法
yxh学长给新生拉的div3水题. . .竟然没想起来咋搞
由于可以通过旋转操作把一段连续的区间和另一段拼合,呢么我们可以简化一下模型,即问源字符串两段没有重合字符的合法子串的和的最长长度。
由于数据范围给的很小,0~20这就是写在脑门子上的状压。
不过当时在测试的时候想的是通过
正解是通过
这种记录方法很妙,因为我们实际上再找一个状态i的子串和其他与它不冲突的子串时,一些不冲突的子串是目标不冲突子串的子集,枚举他们是没有比较意义的。因此我们直接将每一个子串都向以它为子集的字串提交贡献,假如可以提供贡献就会被以它为子集的字串记录(怎么有种树的感觉,儿子向父亲提交状态)。因此我们对状态为i的串,我们可以通过它的互补串
感觉这个状态转移的很妙,这是一种类似状态树的玩意,父集合可以代表所有子状态中最优的,然后通过父集合再向父父集合传递贡献从而降低了时间复杂度。
以及学了一些状压技巧。
具体见代码。
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!